Maximum common subgraph isomorphism problem

In complexity theory, maximum common subgraph-isomorphism (MCS) is an optimization problem that is known to be NP-hard. The formal description of the problem is as follows:

Maximum common subgraph-isomorphism(G1, G2)

The associated decision problem, i.e., given G1, G2 and an integer k, deciding whether G1 contains an induced subgraph of at least k edges isomorphic to an induced subgraph of G2 is NP-complete.

One possible solution for this problem is to build a modular product graph, in which the largest clique represents a solution for the MCS problem.

MCS algorithms have a long tradition in cheminformatics and pharmacophore mapping.

See also

References